#ifndef UNDO_REDO_H
#define UNDO_REDO_H

#include <stdio.h>
#include <cstring>

using namespace std;

const int MAX_LIST_SIZE = 10000;

struct Color {
	int red,green,blue;
	Color(){}
	Color(const int &a,const int &b,const int &c):red(a),green(b),blue(c){}
	Color(const unsigned char &a, const unsigned char &b, const unsigned char &c):red((int)a),green((int)b),blue((int)c){}
	Color(const Color &p):red(p.red),green(p.green),blue(p.blue){}
	~Color(){}
	int setColor(int a, int b, int c){red=a;green=b;blue=c;return 1;}
	int getColor(int &a, int &b, int &c) const {a=red;b=green;c=blue;return 1;}
};

struct Action {
	Color color;
	int pos_r, pos_c,radius;
	
	Action(){}
	Action(int a,int b,int r,const Color &c):pos_r(a),pos_c(b),radius(r),color(c){}
	Action(const Action &a):pos_r(a.pos_r),pos_c(a.pos_c),radius(a.radius),color(a.color){}
	Action(const Action *a):pos_r(a->pos_r),pos_c(a->pos_c),radius(a->radius),color(a->color){}
	~Action(){}
	int getRow() const {return pos_r;}
	int getCol() const {return pos_c;}
	int getR() const {return radius;}
	int getColor(int &a, int &b, int &c) const {return color.getColor(a,b,c);}
};

class ActionBlock {
	public:
		ActionBlock(){m_actions=NULL;}
		ActionBlock(int n, const char *st=0):m_tot(n) {
			m_len=0; m_time=0;
			m_actions = new Action* [n];
		}
		ActionBlock(const ActionBlock &a) {
			clear();
			m_tot=a.m_tot;
			m_time=a.m_time;
			m_actions = new Action* [m_tot];
			for(m_len=0;m_len<m_tot;m_len++)
				m_actions[m_len]=new Action(a.m_actions[m_len]);
		}
		~ActionBlock() {
//			printf("Deleting ActionBlock : %x\n",this);
			clear();
		}

		int clear() {
			clearActions();
			return 1;
		}

		int clearActions() {
			if(m_actions!=NULL)
			{
				for(int i=0;i<m_len;i++)
					if(m_actions[i]!=NULL)
						delete m_actions[i];
				delete m_actions;
			}
			m_actions=NULL;
			m_tot=m_len=m_time=0;
			return 1;
		}

		int addAction(const Action &a) {
			if(m_len>=m_tot)
				return 0;
			m_actions[m_len++]=new Action(a);
			return 1;
		}

		const Action *getAction(int pos) const {
			if(0<=pos&&pos<m_len)
				return m_actions[pos];
			return NULL;
		}

		int getLen() const { return m_len; }
		int getTotal() const { return m_tot; }
		int setTime (int t) {return (m_time=t);}
		int getTime () const {return m_time;}

	private:
		Action **m_actions;
		int m_tot,m_len,m_time;
};

class ActionList {
	public:
		// [ m_head, m_tail )
		ActionList() {
			m_head=0; m_tail=1; m_cur=0;
			memset(m_forward,0,sizeof(m_forward));
			memset(m_backward,0,sizeof(m_backward));
		}
		~ActionList() {
			clearList();
		}

		int clearList() {

			while(m_head!=m_tail)
			{
				deleteActionBlock(m_head);
				inc(m_head);
			}
			deleteActionBlock(m_tail);
			m_head=0; m_tail=1; m_cur=0;

			return 1;
		}

		int push ( ActionBlock *p_for, ActionBlock *p_back ) {

			deleteActionBlock(m_cur,1);
			m_forward[m_cur]=p_for;
			deleteActionBlock(inc(m_cur));
			m_backward[m_cur]=p_back;

			m_tail=(m_cur+1)%MAX_LIST_SIZE;
			deleteActionBlock(m_tail);

			if(m_tail==m_head)
			{
				inc(m_head);
				deleteActionBlock(m_head,2);
			}

			return 1;
		}

		const ActionBlock *undo () {

			ActionBlock *ret=m_backward[m_cur];

			if(ret!=NULL)
				dec(m_cur);

			return ret;
		}

		const ActionBlock *redo () {

			ActionBlock *ret=m_forward[m_cur];

			if(ret!=NULL)
				inc(m_cur);

			return ret;

		}

		bool canUndo() const {return m_backward[m_cur]!=NULL;}
		bool canRedo() const {return m_forward[m_cur]!=NULL;}
		bool updateRedoTime(int p_time) {
			if(canUndo())
				m_forward[(m_cur-1+MAX_LIST_SIZE)%MAX_LIST_SIZE]->setTime(p_time);
			return true;
		}

	private:
		ActionBlock *m_forward[MAX_LIST_SIZE], *m_backward[MAX_LIST_SIZE];
		int m_head, m_tail, m_cur;
		int inc ( int &t ) { t=(t+1)%MAX_LIST_SIZE; return t; }
		int dec ( int &t ) { t=(t-1+MAX_LIST_SIZE)%MAX_LIST_SIZE; return t; }
		int deleteActionBlock ( const int &p, int s=3 ) {
			if(m_forward[p]!=0&&(s&1))
			{
				delete m_forward[p];
				m_forward[p]=NULL;
			}
			if(m_backward[p]!=0&&(s&2))
			{
				delete m_backward[p];
				m_backward[p]=NULL;
			}
			return s;
		}
};

#endif
